package srcInterviewPrep;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Date;
import java.util.HashSet;
import java.util.List;
import java.util.Stack;

import com.sun.xml.internal.bind.v2.runtime.unmarshaller.XsiNilLoader.Array;

import srcInterviewPrep.TortoiseHareCycleDetector.TortoiseHareNode;
import srcInterviewPrep.TortoiseHareCycleDetector.MulLambdaPair;

import srcInterviewPrep.LinkedListReverser.Node;

public class AATestRunner
{
    /**
     * @param args
     */
    public static void main(String[] args)
    {
    	// just adding a test line
        RunLinkedListReverser();
    }

    private static void RunFibonacci() 
    {
        int n = 10;
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        
        for (int i = 1; i <= n; ++i)
        {
            sb1.append(Fibonacci.GetFibNum(i));
            sb1.append(' ');
            sb2.append(Fibonacci.GetFibNumRecursive(i));
            sb2.append(' ');
        }
        
        System.out.println(sb1.toString());
        System.out.println(sb2.toString());
    }

    private static void RunMaxMindGame()
    {
        MaxMindGame.PrintNumHitsAndPsedoHits("RGGB", "YRGB");
    }

    private static void RunSortedListToBSTConverter()
    {
        LinkedListNode llHead = GetSampleLinkedList();

        BTNode btN1 = SortedListToBSTConverter.ConvertListToBST(llHead);

        List<Integer> serializedNums = BinaryTreeSerializer.Serialize(btN1);
        PrintList(serializedNums);
    }

    private static LinkedListNode GetSampleLinkedList()
    {
        // return new LinkedListNode(1);

        LinkedListNode n1 = new LinkedListNode(1);
        LinkedListNode n2 = new LinkedListNode(2);
        LinkedListNode n3 = new LinkedListNode(3);
        LinkedListNode n4 = new LinkedListNode(4);
        LinkedListNode n5 = new LinkedListNode(5);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;

        return n1;
    }

    private static void RunBinaryTreeSerializer()
    {
        //BTNode n1 = GetSampleBTNode1();
        BTNode n1 = GetSampleBTNode2();

        n1.PrintInOrderTraversal();
        System.out.println();

        List<Integer> serializedNums = BinaryTreeSerializer.Serialize(n1);
        PrintList(serializedNums);

        BTNode n = BinaryTreeSerializer.Deserialize(serializedNums);
        n.PrintInOrderTraversal();
        System.out.println();
    }

    private static BTNode GetSampleBTNode1()
    {
        /**
         *          1
         *         / \
         *        2   3
         */
        BTNode n1 = new BTNode(1);
        BTNode n2 = new BTNode(2);
        BTNode n3 = new BTNode(3);

        n1.left = n2;
        n1.right = n3;
        return n1;
    }

    private static BTNode GetSampleBTNode2()
    {
        /**
         * Tree on values:
         *                            5
         *                         /     \
         *                        4        3
         *                      /            \
         *                     2                1
         *                    /  \             / \
         *                   8    7           4   6
         *                  /       \
         *                 9         1
         *
         * Nodes:
         *                            n1
         *                         /     \
         *                        n2        n3
         *                      /            \
         *                     n4              n5
         *                    /  \             / \
         *                   n6    n7         n8   n9
         *                  /       \
         *                 n10       n11

         */

        BTNode n1 = new BTNode(5);
        BTNode n2 = new BTNode(4);
        BTNode n3 = new BTNode(3);
        BTNode n4 = new BTNode(2);
        BTNode n5 = new BTNode(1);
        BTNode n6 = new BTNode(8);
        BTNode n7 = new BTNode(7);
        BTNode n8 = new BTNode(4);
        BTNode n9 = new BTNode(6);
        BTNode n10 = new BTNode(9);
        BTNode n11 = new BTNode(1);

        // Building tree bottom up
        n6.left = n10;

        n7.right = n11;

        n4.left = n6;
        n4.right = n7;

        n2.left = n4;

        n1.left = n2;
        n1.right = n3;

        n3.right = n5;

        n5.left = n8;
        n5.right = n9;

        return n1;
    }

    private static void PrintList(List<Integer> list)
    {
        System.out.println(Arrays.toString(list.toArray()));
    }

    private static void RunSearchInRotatedArray()
    {
        int[] a = { 15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10 , 14 };

        System.out.println(SearchInRotatedArray.FindInRotatedArray(a, 17));
    }

    private static void RunMaxContinousSubArray()
    {
        int[] n = { 1, -1, 2, 3, -10 };

        MaxContinousSubArray.Kadanes(n);

        System.out.println();
        System.out.println("DP solution");
        MaxContinousSubArray.DPBasedSolution(n);
    }

    private static void RunSortedLinkedListMerger()
    {
        LinkedListNode n1 = new LinkedListNode(1);
        LinkedListNode n2 = new LinkedListNode(2);
        LinkedListNode n3 = new LinkedListNode(3);
        LinkedListNode n4 = new LinkedListNode(4);
        LinkedListNode n5 = new LinkedListNode(5);

        n1.next = n3;
        n3.next = n5;

        n2.next = n4;

        LinkedListNode h = SortedLinkedListMerger.MergeSortedLinkedLists(n1, n2);

        System.out.println(h);
    }

    private static void RunStringSerializer()
    {
        String[] strings =
            {
                "a\\\\\\b",
                "b,,,c",
                "ca",
                ""
            };

        System.out.println(Arrays.toString(strings));
        StringSerializer stringSerializer = new StringSerializer();
        String serializedString = stringSerializer.Serialize(Arrays.asList(strings));
        System.out.println(serializedString);

        List<String> deserializedStrings = stringSerializer.Deserialize(serializedString);

        System.out.println(deserializedStrings);
    }

    private static void RunStockSeller()
    {
        double[] prices = {
                55.39, 109.23, 48.29, 81.59, 105.53, 94.45
        };

        StockSeller.PrintBuySellDates(prices);
    }

    private static void RunUgly()
    {
        System.out.println(Arrays.toString(UglyNumber.GetFirstKUglyNumbers(50)));
        System.out.println(Arrays.toString(UglyNumber.getNthUglyNo(50)));
    }

    private static void RunLinkedListReverser()
    {
        Node a = new Node(1);
        Node b = new Node(2);
        Node c = new Node(3);
        a.next = b;
        b.next = c;

        PrintNodes(a);
        Node d = LinkedListReverser.ReverseTailRecursively(a);
        PrintNodes(d);

    }

    private static void PrintNodes(Node n) {
        while (n != null)
        {
            System.out.print(n.data);
            System.out.print(' ');
            n = n.next;
        }
        System.out.println();
    }

    private static void RunTortoiseHare()
    {
        TortoiseHareNode a = new TortoiseHareNode(1);
        TortoiseHareNode b = new TortoiseHareNode(2);
        TortoiseHareNode c = new TortoiseHareNode(3);

        a.next = b;
        b.next = c;
        c.next = a;

        MulLambdaPair pair = TortoiseHareCycleDetector.FindCycle(a);

        System.out.println("mu: " + pair.mu.data);
        System.out.println("lambda: " + pair.lambda);
    }

    private static void RunFloodFill()
    {
        boolean[][] m = {
                { false, true, false, false, true, true },
                { false,true, true, true, false, true },
                { true, true, false, false, true, false },
                {false, true, false, false, true, false }
        };

        int numRows = 4;
        int numCols = 6;

        FloodFill.StartFloodFill(m, 2, 1, numRows, numCols);

        for (int i = numRows-1; i >= 0 ; --i)
        {
            for (int j = 0; j < numCols; ++j)
            {
                System.out.print(m[i][j]);
                System.out.print(' ');
            }

            System.out.println();
        }
    }

    private static void RunNBitAdder()
    {
        char[] a = "110101101".toCharArray();
        char[] b = "010101011".toCharArray();

        System.out.println("1001011000");
        System.out.println(NBitAdder.AddBits(a, b));
    }

    private static void RunPowerModulo()
    {
        int x = 5;
        int y = 13;
        int z = 6;

        System.out.println(PowerModulo.CalculatePowerModulo(x, y, z));
        System.out.println(Math.pow(x, y)%z);


    }

    private static void RunStressJobScheduler()
    {
        int [] l = { 10, 1, 10, 10 };
        int [] h = { 5, 50, 5, 1 };

        System.out.println(StressJobScheduler.GetOptimalScheduleValue(l, h));
        System.out.println(StressJobScheduler.GetOptimalScheduleValueV2(l, h));
    }

    private static void RunSubsetSum()
    {
        /*
        int[] nums = {
                9, 3, 11, 6, 55, 9, 7, 3, 29, 16, 4, 4,
                20, 11, 6, 6, 8, 8, 4, 10, 11, 16, 10, 6,
                10, 3, 5, 6, 4, 14, 5, 29, 15, 3, 18, 7, 7,
                20, 4, 9, 3, 11, 38, 6, 3, 13, 12, 5, 10, 3, 3 };

        int sum = 269;

        */

        int[] nums = { 10, 15, 20, 5, 5 };
        int sum = 20;

        System.out.println(SubsetSum.GetNumSubsets(nums, sum));
    }

    private static void RunTernaryTree()
    {
        TernaryTree tree = new TernaryTree();

        tree.Insert(5);
        tree.Insert(4);
        tree.Insert(9);
        tree.Insert(5);
        tree.Insert(7);
        tree.Insert(2);
        tree.Insert(2);

        tree.Insert(6);
        tree.Insert(8);
        tree.Insert(12);
        tree.Insert(10);
        tree.Insert(17);
        tree.PrintPreOrderTraversal();

        tree.Delete(9);
        tree.PrintPreOrderTraversal();
    }

    private static void RunTestProgram()
    {
        Date d = new Date();

        System.out.println(d);
    }

    private static Object Foo(Object a)
    {
        return null;
    }

    private static void RunStringToLongConverter()
    {
        String s = "-922337203685477580";

        long n = StringToLongConverter.StringToLong(s);

        System.out.println(s);
        System.out.println(n);
    }

    private static void RunBitShift()
    {
        System.out.println(add_no_arithm(3, 5));
    }

    private static int add_no_arithm(int a, int b) {
        if (b == 0) return a;
        int sum = a ^ b; // add without carrying
        int carry = (a & b) << 1; // carry, but don’t add
        return add_no_arithm(sum, carry); // recurse
        }

    private static void RunBoggle()
    {
        char[][] m =
            {
                { 'A', 'S', 'T', 'O' },
                { 'E', 'W', 'B', 'X' },
                { 'A', 'M', 'L', 'O' },
                { 'F', 'X', 'I', 'E' }
            };

        int n = 4;

        HashSet<String> dict = new HashSet<String>();
        dict.add("BOX");
        dict.add("LIOB");
        dict.add("SIT");

        System.out.println(Boggle.GetAllBoggleWords(dict, m, n, n));
    }

    private static void RunLowestCommonSubsequence()
    {
        String s1 = "BARTHOLEMEWSIMPSON";
        String s2 = "KRUSTYTHECLOWN";
        char[] a = s1.toCharArray();
        char[] b = s2.toCharArray();

        System.out.println(LongestCommonSubsequence.FindLCSLength(a, b));
    }

    private static void RunKnapSack()
    {
        int n = 3;
        int w = 4;

        Item[] items = new Item[]
                {
                    new Item(0, 1, 1),
                    new Item(1, 2, 2),
                    new Item(2, 2, 2),
                };

        List<Item> selectedItems = new ArrayList<Item>();

        System.out.println(KnapSack.GetKnapSack(items, w, selectedItems));
        System.out.println(selectedItems);
    }

    private static void RunMergeSort()
    {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(2);
        list.add(8);
        list.add(5);
        list.add(4);
        list.add(1);
        list.add(10);

        System.out.println(MergeSort.Sort(list, 0, list.size() - 1));
    }

    private static void RunSubsequenceMatching()
    {
        char[] str1 = { 'b', 'a', 'b', 'a' };
        char[] str2 = { 'a', 'b', 'b', 'a' };

        System.out.println(SubsequenceMatching.IsSubsequence(str1, str2));
    }

    private static void RunIntervalAssignment()
    {
        Interval i0 = new Interval(0, 1, 5);
        Interval i1 = new Interval(1, 2, 8);
        Interval i2 = new Interval(2, 3, 4);
        Interval i3 = new Interval(3, 6, 10);

        Interval[] intervals = new Interval[4];
        intervals[0] = i0;
        intervals[1] = i1;
        intervals[2] = i2;
        intervals[3] = i3;

        System.out.println(IntervalAssignment.AssignProcessors(intervals));
    }


    private static void RunIntervalScheduling()
    {
        Interval i1 = new Interval(1, 1, 5);
        Interval i2 = new Interval(2, 2, 8);
        Interval i3 = new Interval(3, 3, 4);
        Interval i4 = new Interval(4, 6, 10);

        List<Interval> intervals = new ArrayList<Interval>();
        intervals.add(i1);
        intervals.add(i2);
        intervals.add(i3);
        intervals.add(i4);

        System.out.println(IntervalScheduling.ScheduleIntervals(intervals));
    }

    private static void RunFindInSortedMatrix()
	{
		int[][] matrix = {
				{ 1, 3, 5, 7, 9 },
				{ 4, 11, 12, 13, 14 },
				{ 6, 13, 14, 15, 18 },
				{ 8, 15, 17, 19, 20 }
			};

		int elem = 16;

		// System.out.println(FindInSortedMatrix.DivideAndConquerFind(matrix, elem, 0, 0, 3, 4));
		System.out.println(FindInSortedMatrix.FindDiagonal(matrix, elem, 3, 4));
	}

	private static void RunBipartiteChecker() {
		Vertex v1 = new Vertex(1, 0, new ArrayList<Vertex>());
        Vertex v2 = new Vertex(2, 0, new ArrayList<Vertex>());
        Vertex v3 = new Vertex(3, 0, new ArrayList<Vertex>());
        Vertex v4 = new Vertex(4, 0, new ArrayList<Vertex>());
        Vertex v5 = new Vertex(5, 0, new ArrayList<Vertex>());
        Vertex v6 = new Vertex(6, 0, new ArrayList<Vertex>());
        Vertex v7 = new Vertex(7, 0, new ArrayList<Vertex>());
        Vertex v8 = new Vertex(8, 0, new ArrayList<Vertex>());
        Vertex v9 = new Vertex(9, 0, new ArrayList<Vertex>());
        Vertex v10 = new Vertex(10, 0, new ArrayList<Vertex>());

        v1.Neighbors().add(v6);
        v6.Neighbors().add(v1);

        v1.Neighbors().add(v7);
        v7.Neighbors().add(v1);

        v2.Neighbors().add(v3);
        v3.Neighbors().add(v2);

        v2.Neighbors().add(v4);
        v4.Neighbors().add(v2);

        v4.Neighbors().add(v5);
        v5.Neighbors().add(v4);

        v3.Neighbors().add(v8);
        v8.Neighbors().add(v3);

        v8.Neighbors().add(v9);
        v9.Neighbors().add(v8);

        v8.Neighbors().add(v10);
        v10.Neighbors().add(v8);

        v3.Neighbors().add(v5);
        v5.Neighbors().add(v3);

        v3.Neighbors().add(v4);
        v4.Neighbors().add(v3);

        List<Vertex> vertices = new ArrayList<Vertex>();
        vertices.add(v1);
        vertices.add(v2);
        vertices.add(v3);
        vertices.add(v4);
        vertices.add(v5);
        vertices.add(v6);
        vertices.add(v7);
        vertices.add(v8);
        vertices.add(v9);
        vertices.add(v10);

        System.out.println(BipartiteChecker.IsGraphBipartite(vertices));
	}

	private static void RunTopologicalSort()
	{
		// need a directed graph

		Vertex v1 = new Vertex(1, 0, new ArrayList<Vertex>());
        Vertex v2 = new Vertex(2, 0, new ArrayList<Vertex>());
        Vertex v3 = new Vertex(3, 0, new ArrayList<Vertex>());
        Vertex v4 = new Vertex(4, 0, new ArrayList<Vertex>());
        Vertex v5 = new Vertex(5, 0, new ArrayList<Vertex>());
        Vertex v6 = new Vertex(6, 0, new ArrayList<Vertex>());
        Vertex v7 = new Vertex(7, 0, new ArrayList<Vertex>());
        Vertex v8 = new Vertex(8, 0, new ArrayList<Vertex>());
        Vertex v9 = new Vertex(9, 0, new ArrayList<Vertex>());
        Vertex v10 = new Vertex(10, 0, new ArrayList<Vertex>());

        v1.Neighbors().add(v6);

        v1.Neighbors().add(v7);

        v2.Neighbors().add(v3);

        v2.Neighbors().add(v4);

        v4.Neighbors().add(v5);

        v3.Neighbors().add(v8);

        v8.Neighbors().add(v9);

        v8.Neighbors().add(v10);

        v3.Neighbors().add(v5);

        v3.Neighbors().add(v4);


        List<Vertex> vertices = new ArrayList<Vertex>();
        vertices.add(v1);
        vertices.add(v2);
        vertices.add(v3);
        vertices.add(v4);
        vertices.add(v5);
        vertices.add(v6);
        vertices.add(v7);
        vertices.add(v8);
        vertices.add(v9);
        vertices.add(v10);

        System.out.println(TopologicalSort.SortTopologically(vertices));
	}

}
